/* 字符串相关操作:
反转字符串
判断一个整数是否是回文数
判断两个字符串是否为变形词（内容一样，顺序不一样）
判断两个字符串是否互为旋转词
判断字符数组中是否所有的字符都只出现过一次
翻转字符串中单词顺序
找到字符串的最长无重复字符子串
KMP算法
 */
 
//反转字符串
public static String strReverseWithArray(String string){
	if(string==null||string.length()==0){
		return string;
	}
	int length = string.length();
	char[] array = new char[length];
	for(int i=0;i<length;i++){
		array[i] = string.charAt(length-1-i);
	}
	return new String(array);
}
public static String strReverseWithStack(String string){
	if(string==null||string.length()==0){
		return string;
	}
	Stack<Character> stringStack = new Stack<>();
	char[] array = string.toCharArray();
	for(Character c:array){
		stringStack.push(c);
	}
	int length = string.length();
	for(int i=0;i<length;i++){
		array[i] = stringStack.pop();
	}
	return new String(array);
}
public static String strReverseWithXor(String string){
	if(string==null||string.length()==0){
		return string;
	}
	char[] array = string.toCharArray();
	int length = string.length()-1;
	for(int i=0;i<length;i++;length--){
		array[i]^=array[length];
		array[length]^=array[i];
		array[i]^=array[length];
	}
	return new String(array);
}
public static strReverseWithRecursive(String string){
	if(string==null||string.length()==0){
		return string;
	}
	int length = string.length();
	if(length==1){
		return string;
	}else{
		return strReverseWithRecursive(string.substring(1))+string.charAt(0);
	}	
}

//判断一个整数是否是回文数
public boolean isPalindrome(int n){
	if(n==Integer.MIN_VALUE){
		return false;
	}
	int help = 1;
	n = Math.abs(n);
	while(n/help>=10){
		help*=10;
	}
	while(n!=0){
		if(n/help!=n%10){
			return false;
		}
		n = (n%help)/10;
		help/=100;
	}
	return true;
}

//判断两个字符串是否为变形词（内容一样，顺序不一样）
public boolean isDeformation(String str1, String str2){
	if(str1==null||str2==null||str1.length()!=str2.length()){
		return false;
	}
	char[] chas1 = str1.toCharArray();
	char[] chas2 = str2.toCharArray();
	int[] map = new int[256];
	for(int i=0;i<chas1.length;i++){
		map[chas1[i]]++;
	}
	for(int i=0;i<chas2.length;i++){
		if(map[chas2[i]]==0){
			return false;
		}else{
			map[chas2[i]]--;
		}
	}
	return true;
}

//判断两个字符串是否互为旋转词
public boolean isRotation(String a, String b){
	if(a==null||b==null||a.length()!=b.length()){
		return false;
	}
	String b2 = b + b;
	return getIndexOf(b2,a)!=-1; //getIndexOf函数是KMP算法的实现
}

//判断字符数组中是否所有的字符都只出现过一次
public boolean isUnique(char[] chas){
	if(chas == null){
		return true;
	}
	boolean[] map = new boolean[256];
	for(int i = 0;i<chas.length;i++){
		if(map[chas[i]]){
			return false;
		}
		map[chas[i]]=true;
	}
	return true;
}

//翻转字符串中单词顺序
public void rotateWord(char[] chas){
	if(chas==null || chas.length==0){
		return;
	}
	reverse(chas,0,chas.length-1);
	int l = -1;
	int r = -1;
	for(int i=0;i<chas.length;i++){
		if(chas[i]!=''){
			l=i==0||chas[i-1]==''?i:l;
			r=i==chas.length-1||chas[i+1]==''?i:r;
		}
		if(l!=-1&&r!=-1){
			reverse(chas,l,r);
			l=-1;
			r=-1;
		}
	}
}
public void reverse(char[] chas, int start,int end){
	char tmp = 0;
	while(start<end){
		tmp = chas[start];
		chas[start] = chas[end];
		chas[end] = tmp;
		start++;
		end--;
	}
}

//找到字符串的最长无重复字符子串
public int maxUnique(String str){
	if(str==null ||str.equals("")){
		return 0;
	}
	char[] chas = str.toCharArray();
	int[] map = new int[256];
	for(int i=0;i<256;i++){
		map[i]=-1;
	}
	int len =0;
	int pre = -1;
	for(int i =0;i<chas.length;i++){
		pre = Math.max(pre,map[chas[i]]);
		len = Math.max(len,i-pre);
		map[chas[i]] = i;
	}
	return len;	
}

//KMP算法
public int getIndexOf(String s,String m){
	if(s==null||m==null||m.length()<1||s.length()<m.length()){
		return -1;
	}
	char[] ss = s.toCharArray();
	char[] ms = m.toCharArray();
	int si = 0;
	int mi = 0;
	int[] next = getNextArray();
	while(si<ss.length &&mi<ms.length){
		if(ss[si]==ms[mi]){
			si++;
			mi++;
		}else if(next[mi]==-1){
			si++;
		}else{
			mi = next[mi];
		}
	}
	return mi==ms.length?si-mi:-1;
}
public int[] getNextArray(char[] ms){
	if(ms.length==1){
		return new int[]{-1};
	}
	int[] next = new int[ms.length];
	next[0] = -1;
	next[1] = 0;
	int pos = 2;
	int cn = 0;
	while(pos<next.length){
		if(ms[pos-1]==ms[cn]){
			next[pos++] = ++cn;
		}else if(cn>0){
			cn = next[cn];
		}else{
			next[pos++]=0;
		}
	}
	return next;
}
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 